#!/usr/bin/python3

import random
from typing import Callable


def swap(items: list[int], a: int, b: int):
    """
    交换列表中，给定下标的两个元素。
    """
    items[a], items[b] = items[b], items[a]


def quick_sort(items: list[int]):
    """
    docstring
    """
    quick_sort_helper(items, 0, len(items) - 1)


def quick_sort_helper(items: list[int], p: int, r: int) -> None:
    """
    快速排序
    """
    if p < r:
        i: int = partition(items, p, r)
        quick_sort_helper(items, p, i - 1)
        quick_sort_helper(items, i + 1, r)


def partition(items: list[int], low: int, high: int) -> int:
    """
    划分
    :low int 地位索引；
    :high int 高位索引；
    """
    i: int = low
    j: int = high

    while i < j:
        # 将地位取做枢纽值，暂存；
        povit: int = items[i]

        # 自高位向低位，找到比枢纽值小的值；
        while items[j] >= povit and i < j:
            j -= 1

        # 将其存储到低位；
        items[i] = items[j]

        # 自高位向低位，找到比枢纽值大的值；
        while items[i] <= povit and i < j:
            i += 1

        # 将其存储到高位；
        items[j] = items[i]

    # 枢纽值到位；
    items[i] = povit

    return i


def main(size: int = 10, sort: Callable = quick_sort):
    """
    docstring
    """
    lyst: int = []
    for count in range(size):
        lyst.append(random.randint(1, 99))

    print(lyst)
    sort(lyst)
    print(lyst)


if __name__ == "__main__":
    main(sort=quick_sort)
